package com.leetcode.No1838;

import org.junit.Test;

import java.util.HashMap;

/**
 * @program: leetcode
 * @description: 最高频元素的频数
 * @author: wangzhihua
 * @date: 2021-07-19
 */
public class Solution {

	@Test
	public void test01() {
//		System.out.println(maxFrequency(new int[]{1,2,4}, 5));
//		System.out.println(maxFrequency(new int[]{1,4,8,13}, 5));
//		System.out.println(maxFrequency(new int[]{3,9,6}, 2));
		System.out.println(maxFrequency(new int[]{9930, 9923, 9983, 9997, 9934, 9952, 9945, 9914, 9985, 9982, 9970, 9932, 9985, 9902, 9975, 9990, 9922, 9990, 9994, 9937, 9996, 9964, 9943, 9963, 9911, 9925, 9935, 9945, 9933, 9916, 9930, 9938, 10000, 9916, 9911, 9959, 9957, 9907, 9913, 9916, 9993, 9930, 9975, 9924, 9988, 9923, 9910, 9925, 9977, 9981, 9927, 9930, 9927, 9925, 9923, 9904, 9928, 9928, 9986, 9903, 9985, 9954, 9938, 9911, 9952, 9974, 9926, 9920, 9972, 9983, 9973, 9917, 9995, 9973, 9977, 9947, 9936, 9975, 9954, 9932, 9964, 9972, 9935, 9946, 9966}, 3056));
	}

	public int maxFrequency(int[] nums, int k) {
		for (int i = 0; i < nums.length; ++i) {
			nums[i] -= 9900;
		}
		HashMap<Integer, Integer> map1 = new HashMap<Integer, Integer>();
		for (int i = 0; i < nums.length; ++i) {
			map1.put(nums[i], map1.get(nums[i]) == null ? 1 : (map1.get(nums[i]) + 1));
		}

		sort(nums, 0, nums.length - 1);

		HashMap<Integer, Integer> map2 = new HashMap<Integer, Integer>();
		for (int i = 0; i < nums.length; ++i) {
			map2.put(nums[i], map2.get(nums[i]) == null ? 1 : (map2.get(nums[i]) + 1));
		}
		for (Integer i : map2.keySet()) {
			System.out.println("[map1] " + i + ": " + map1.get(i));
			System.out.println("[map2] " + i + ": " + map2.get(i));
			if (!map1.get(i).equals(map2.get(i))) {
				System.out.println("**************************************");
			}
			System.out.println("===========================");
		}

		int previousIndex = 0;
		int usedK = 0; // <= k
		int tmpAns = 1;
		int ans = 1;
		for (int i = 1; i < nums.length; ++i) {
			usedK += (i - previousIndex) * (nums[i] - nums[i - 1]);
			if (usedK <= k) {
				ans = Math.max(ans, ++tmpAns);
				continue;
			}
			while (previousIndex < i && usedK > k) {
				usedK -= nums[i] - nums[previousIndex++];
			}
			tmpAns = i - previousIndex + 1;
		}
		return ans;
	}

	public void sort(int[] nums, int left, int right) {
		if (nums == null || nums.length <= 1 || left >= right) {
			return;
		}
		int anchorNum = nums[left];
		int anchorLeft = left;
		int anchorRight = right;
		do {
			while (left < right && anchorNum <= nums[right]) {
				--right;
			}
			nums[left] = nums[right];
			while (left < right && nums[left] <= anchorNum) {
				++left;
			}
			nums[right] = nums[left];
		} while (left < right);
		// 此时left=right
		nums[left] = anchorNum;
		sort(nums, anchorLeft, right - 1);
		sort(nums, left + 1, anchorRight);
	}

}
